class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Test {
    /*
    题目 1：反转链表
     */
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;
        }
        return pre;
    }

    /*
    题目 2: 链表内指定区间的反转！
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // 设置一个 哑节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode frontNode = dummyNode;
        ListNode firstNode = dummyNode;

        for(int i = 0; i < m - 1; i++){
            frontNode = frontNode.next;
        }

        firstNode = frontNode.next;

        ListNode lastNode = dummyNode;

        for(int i = 0; i <= n; i++){
            lastNode = lastNode.next;
        }

        for(int i = 0; i <= n - m; i++){
            ListNode node = new ListNode(firstNode.val);
            node.next = lastNode;
            lastNode = node;
            firstNode = firstNode.next;
        }

        frontNode.next = lastNode;

        return dummyNode.next;
    }

    /*
    题目 3：链表中的节点每 k 个一组翻转
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        ListNode tail = head;
        for(int i = 0; i < k; i++){
            if(tail == null){
                return head;
            }
            tail = tail.next;
        }

        ListNode pre = null;
        ListNode cur = head;

        while(cur != tail){
            ListNode curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;
        }

        head.next = reverseKGroup(tail, k);
        return pre;
    }



}
